package org.review.algorithm.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class MergeSort {
    public static void main(String[] args) {
     /*   int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        impl(arr, 0, arr.length - 1, new int[arr.length]);

        for (int i : arr) {
            System.out.print(i + " ");
        }*/

        int size = 200000;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * size * 10); // 生成一个[0, 8000000) 数
        }

        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        String date1Str = simpleDateFormat.format(new Date());
        Arrays.stream(arr).mapToObj(e -> e + " ")
                .forEach(System.out::print);
        System.out.println("排序前的时间是=" + date1Str);
        impl(arr, 0, arr.length - 1, new int[arr.length]);
        //quickSort(arr, 0, arr.length - 1);
        String date2Str = simpleDateFormat.format(new Date());
        System.out.println("排序后的时间是=" + date2Str);
        Arrays.stream(arr).mapToObj(e -> e + " ")
                .forEach(System.out::print);

    }

    public static void impl(int[] arr, int left, int right, int[] list) {
        if (left >= right) return;
        int l = left, r = right, mid = (left + right) / 2;
        //TODO 2024/8/30: 先分解到最小
        impl(arr, left, mid, list);
        impl(arr, mid + 1, right, list);
        merge(arr, left, right, mid, list);
    }

    private static void merge(int[] arr, int left, int right, int mid, int[] list) {
        int r = mid + 1, l = left;
        int varIndex = left;
        //TODO 2024/8/30: 合并队列需要借助一个临时数组，一个while，退出条件两个有序队列下表=length，
        while (l <= mid && r <= right) {

            if (arr[l] < arr[r]) {
                list[varIndex++] = arr[l];
                l++;
            } else {   //TODO 2024/9/7: if (arr[l] >= arr[r])
                list[varIndex++] = arr[r];
                r++;
            }
        }

        while (l <= mid) {
            list[varIndex++] = arr[l++];
        }
        while (r <= right) {
            list[varIndex++] = arr[r++];
        }

        varIndex--;//TODO 2024/9/5:因为上边每次都是先添加后++，因此这里指向的是下一个索引
        while (left <= varIndex) {
            arr[varIndex] = list[varIndex];
            varIndex--;
        }

     /*   varIndex = 0;
        while (left <= right) {
            arr[left++] = list[varIndex++];
        }*/
    }
}
